COURS : Classification

OBJECTIFS D’APPRENTISSAGE

Introduction

Les objectifs de ce cours sont :

• Comprendre la nature générale d’une procédure de classification non supervisée
• Construire une matrice de dissimilarité à partir d’un tableau à 1, 2 ou k dimension
• Appliquer la procédure k-means
• Construire une classification ascendante hiérarchique à l’aide du critère de Ward
• Comprendre le lien entre ACP et CAH

La classification consiste d’une manière générale à regrouper dans une même classe des individus qui se ressemblent et à séparer dans des classes différentes ceux qui sont différents. Ce problème très général est au coeur même de toute démarche scientifique et il soulève des questions épistémologiques et philosophiques fondamentales qui dépassent le cadre de cet enseignement. Nous nous limiterons ici à poser le problème de la classification dans le cadre de procédures statistiques appliquées à des variables de type quantitatif continu. Nous montrerons que le problème posé est alors celui de la recherche d’une classification non supervisée c’est-à-dire la découverte de ressemblances entre des individus en fonction de critères objectivement reproductibles.

UNE DIMENSION

Considérons à titre de premier exemple la consommation moyenne d’alcool (mesurée en kCal/pers/j) de 9 régions d’Europe et d’Afrique

Exemple 1 : variable unique

	region	Alcool
1	Afrique australe	101
2	Afrique centrale	39
3	Afrique occidentale	21
4	Afrique orientale	35
5	Afrique septentrionale	4
6	Europe méridionale	145
7	Europe occidentale	176
8	Europe orientale	160
9	Europe septentrionale	146

Essayons de répondre à des questions d’abord à des questions simples comme :

• Q1 : quelles sont les deux régions les plus dissemblantes ?
• Q2 :l’Afrique Occidentale ressemble-t-elle plus à l’Afrique septentrionale ou à l’Afrique Australe ?

Puis à des questions plus complexes comme :

• Q3 : Quelle est la meilleure partition en deux classes ?

• Q4 : Quelle est la meilleure partition en k classes ?

• La question Q1 est la plus simple et sa réponse ne devrait pas susciter de débat. sachant que la valeur miniumum est de 4 et la valeur maximale de 176, on peut conclure que la plus grande différence est observée entre l’Afrique septentrionale (point n°5) et l’Europe occidentale (point n°7). On peut visualiser leuer éloignement à l’aide d’une figure :

• La question Q2 est en revanche moins simple qu’il n’y paraît car elle peut appeler des réponses différentes selon que l’on décide d’utiliser des différences absolues ou des différences relatives entre les régions.

Distance absolue

Si l’on raisonne en valeur absolue, nous allons construire une matrice de dissimilarité \(D_{abs}\) définie par :

\(D_{abs}(i,j) = \lvert{X_i-X_j}\rvert\)

Matrice des différences absolues

	1	2	3	4	5	6	7	8	9
1. Afrique australe	0	62	80	66	97	44	75	59	45
2. Afrique centrale	62	0	18	4	35	106	137	121	107
3. Afrique occidentale	80	18	0	14	17	124	155	139	125
4. Afrique orientale	66	4	14	0	31	110	141	125	111
5. Afrique septentrionale	97	35	17	31	0	141	172	156	142
6. Europe méridionale	44	106	124	110	141	0	31	15	1
7. Europe occidentale	75	137	155	141	172	31	0	16	30
8. Europe orientale	59	121	139	125	156	15	16	0	14
9. Europe septentrionale	45	107	125	111	142	1	30	14	0

On serait alors tenté de dire que l’Afrique occidentale ressemble plus à l’Afrique septentrionale qu’à l’Afrique Australe puisque les distances observées sont de 17 dans le premier cas et de 80 dans le second.

Distance relative

Mais on pourrait aussi considérer la distance relative en effectuant pour chaque paire de valeur le rapport entre le maximum et le maximum. Soit la matrice de distance relative \(D_{rel}\) définie par :

\(D_{rel}(i,j) = \frac{max(X_i,X_j)}{min(X_i,X_j)}\)

Matrice des différences relatives

	1	2	3	4	5	6	7	8	9
1. Afrique australe	1.00	2.59	4.81	2.89	25.25	1.44	1.74	1.58	1.45
2. Afrique centrale	2.59	1.00	1.86	1.11	9.75	3.72	4.51	4.10	3.74
3. Afrique occidentale	4.81	1.86	1.00	1.67	5.25	6.90	8.38	7.62	6.95
4. Afrique orientale	2.89	1.11	1.67	1.00	8.75	4.14	5.03	4.57	4.17
5. Afrique septentrionale	25.25	9.75	5.25	8.75	1.00	36.25	44.00	40.00	36.50
6. Europe méridionale	1.44	3.72	6.90	4.14	36.25	1.00	1.21	1.10	1.01
7. Europe occidentale	1.74	4.51	8.38	5.03	44.00	1.21	1.00	1.10	1.21
8. Europe orientale	1.58	4.10	7.62	4.57	40.00	1.10	1.10	1.00	1.10
9. Europe septentrionale	1.45	3.74	6.95	4.17	36.50	1.01	1.21	1.10	1.00

On aboutit désormais à une conclusion inverse. En effet le rapport de consommation d’alcool est de 1 à 4.81 dans le cas de l’Afrique australe et de 1 à 5.25 dans le cas del’Afrique septentrionale.

Distance logarithmique

On aurait pu aboutir à la même conclusion en calculant les différences absolues entre les logarithmes des valeurs respectives de Xi et Xj soit la matrice \(D_{log}\) :

\(D_{log}(i,j) = \lvert{log(X_i)-log(X_j)}\rvert\)

Matrice des différences logarithmiques

	1	2	3	4	5	6	7	8	9
1. Afrique australe	0.00	0.95	1.57	1.06	3.23	0.36	0.56	0.46	0.37
2. Afrique centrale	0.95	0.00	0.62	0.11	2.28	1.31	1.51	1.41	1.32
3. Afrique occidentale	1.57	0.62	0.00	0.51	1.66	1.93	2.13	2.03	1.94
4. Afrique orientale	1.06	0.11	0.51	0.00	2.17	1.42	1.62	1.52	1.43
5. Afrique septentrionale	3.23	2.28	1.66	2.17	0.00	3.59	3.78	3.69	3.60
6. Europe méridionale	0.36	1.31	1.93	1.42	3.59	0.00	0.19	0.10	0.01
7. Europe occidentale	0.56	1.51	2.13	1.62	3.78	0.19	0.00	0.10	0.19
8. Europe orientale	0.46	1.41	2.03	1.52	3.69	0.10	0.10	0.00	0.09
9. Europe septentrionale	0.37	1.32	1.94	1.43	3.60	0.01	0.19	0.09	0.00

Ce résultat est logique si on se rappelle que :

\(log(\frac{X_i}{X_j}) = log(X_i) - log(X_j)\)

Les valeurs affichées dans cette troisième matrice ne sont donc rien d’autre que les logarithmes des valeurs de la seconde matrice.

Distance euclidienne (au carré)

Présentons pour finir une quatrième matrice de distance correspondant au carré des différences entre les valeurs que nous nommerons distance euclidienne au carré :

\(D_{euc}^2(i,j) = (X_i-X_j)^2\)

Matrice des différences euclidiennes au carré

	1	2	3	4	5	6	7	8	9
1. Afrique australe	0	3844	6400	4356	9409	1936	5625	3481	2025
2. Afrique centrale	3844	0	324	16	1225	11236	18769	14641	11449
3. Afrique occidentale	6400	324	0	196	289	15376	24025	19321	15625
4. Afrique orientale	4356	16	196	0	961	12100	19881	15625	12321
5. Afrique septentrionale	9409	1225	289	961	0	19881	29584	24336	20164
6. Europe méridionale	1936	11236	15376	12100	19881	0	961	225	1
7. Europe occidentale	5625	18769	24025	19881	29584	961	0	256	900
8. Europe orientale	3481	14641	19321	15625	24336	225	256	0	196
9. Europe septentrionale	2025	11449	15625	12321	20164	1	900	196	0

A première vue cette quatrième mesure de dissimilarité n’a pas grand intérêt puisqu’elle ne fait que reprendre les distances absolues en renforçant leur effet. La distance entre Afrique occidentale et Afrique australe est désormais de \(80^2 = 6400\) tandis que celle entre Afrique occidentale et Afrique septentrionale est de \(17^2 = 289\).

En réalité, cette dernière mesure de distance est l’une des plus utilisée dans les méthodes de classification car elle permet d’établir un lien entre la notion de dissimilarité et la notion de variance. La somme de la matrice des distances euclidiennes au carré est en effet proportionelle à la variance de la variable X puisque :

\({var}(X) = \frac{1}{n-1}\sum_{i=1}^n{(X_i-\overline{X})^2} = \frac{1}{2.n.(n-1)}\sum_{i=1}^n\sum_{j=1}^n{(X_i-X_j)^2}\)

Ce que l’on peut vérifier facilement en calculant la variance de notre indicateur (4541.111) et en la comparant au total de la matrice des distances euclidiennes au carré (653920). Puis en effectuant le calcul \(4541.111 \times 9 \times 8 \times 2 = 653920\)

Partition optimale en deux classes

La recherche d’une partition optimale en deux classes dans un espace à une dimension est relativement simple mais elle impose de se fixer une règle précise de décision, c’est-à-dire un critère de performance à optimiser. D’une manière générale, ce critère devra répondre à la défintion proposée en introduction à savoir :

• regrouper les unités qui se ressemblent le plus entre elles
• séparer les unités qui sont les plus différentes entre elles.

Au vu de la distribution de notre variable, il semble assez évident que nous allons regrouper ensemble les quatres régions d’Europe (n°6,7,8,9) à forte consommation d’alcool et les quatre régions d’Afrique (n°2,3,4,5) à faible consommation. Mais on peut hésiter sur l’affectation de la région n°1 qui se situe à peu près à mi-chemin entre les deux groupes. Faut-il couper en A (trait rouge) ou en B (trait bleu) ?

Une manière statistique de trancher entre les deux solutions consiste à utiliser l’analyse de variance et de tester la part de variance expliquée par un modèle rattachant le point central soit à l’Europe (on coupe en A), soit à l’Afrique (on coupe en B). On construit donc le tableau suivant :

region	Alcool	Classes_2A	Classes_2B
Afrique australe	101	CL2	CL1
Afrique centrale	39	CL1	CL1
Afrique occidentale	21	CL1	CL1
Afrique orientale	35	CL1	CL1
Afrique septentrionale	4	CL1	CL1
Europe méridionale	145	CL2	CL2
Europe occidentale	176	CL2	CL2
Europe orientale	160	CL2	CL2
Europe septentrionale	146	CL2	CL2

Call:
lm(formula = don$Alcool ~ don$Classes_2A)

Residuals:
   Min     1Q Median     3Q    Max 
-44.60  -3.75   0.40  14.25  30.40 

Coefficients:
                  Estimate Std. Error t value Pr(>|t|)    
(Intercept)          24.75      11.76   2.104  0.07342 .  
don$Classes_2ACL2   120.85      15.78   7.658  0.00012 ***
---
Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

Residual standard error: 23.52 on 7 degrees of freedom
Multiple R-squared:  0.8934,    Adjusted R-squared:  0.8781 
F-statistic: 58.64 on 1 and 7 DF,  p-value: 0.0001204

Analysis of Variance Table

Response: don$Alcool
               Df Sum Sq Mean Sq F value    Pr(>F)    
don$Classes_2A  1  32455   32455  58.644 0.0001204 ***
Residuals       7   3874     553                      
---
Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

Call:
lm(formula = don$Alcool ~ don$Classes_2B)

Residuals:
   Min     1Q Median     3Q    Max 
-36.00 -11.75  -5.00   3.25  61.00 

Coefficients:
                  Estimate Std. Error t value Pr(>|t|)    
(Intercept)          40.00      13.14   3.045 0.018708 *  
don$Classes_2BCL2   116.75      19.70   5.926 0.000584 ***
---
Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

Residual standard error: 29.37 on 7 degrees of freedom
Multiple R-squared:  0.8338,    Adjusted R-squared:   0.81 
F-statistic: 35.11 on 1 and 7 DF,  p-value: 0.0005843

Analysis of Variance Table

Response: don$Alcool
               Df  Sum Sq Mean Sq F value    Pr(>F)    
don$Classes_2B  1 30290.1 30290.1  35.112 0.0005843 ***
Residuals       7  6038.8   862.7                      
---
Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1

L’analyse des résultats montre que la solution A est la meilleure dans la mesure où elle a boutit à 89.4% de variance expliquée (donc interclasse) et 10.6% de variance résiduelle (donc intraclasse). La solution B n’arrive qu’à 83.4% de variance interclasse contre 16.6% de variance intraclasse.

Il semble donc plus intéressant de regrouper l’Afrique australe avec les pays européens si le critère à optimiser est la variance c’est-à-dire la somme des distances euclidiennes élevées au carré. Les conclusion auraient évidemment pu être différentes si nous avions adopté un autre critère.

Partition optimale en k-classes

Supposons maintenant que nous cherchions à diviser notre variable en quatre classes, quelle serait la solution optimale en conservant le critère précédent de minimisation de la variance intra-classe et de maximisation de la variance inter-classe ?

Le problème posé est d’une grande complexité mathématique lorsqu’il s’applique à de grand tableaux de données. On utilise le plus souvent des algorithmes comme celui de Jenks pour trouver la meilleure solution possible. Parmi les méthodes facilement accessibles dans R-base pour des tableaux de petite taille, ont peut souligner l’intérêt de la méthode des noyaux mobiles qui consiste à tirer au hasard plusieurs centres de classes et à regrouper autour d’eux les éléments les plus proches jusqu’à atteindre une convergence. En répétant les tirages à sort, on peut espérer se rapprocher de la solution optimale.

Dans notre exemple, on active la procédure k-means pour 100 tirages au sort :

	region	Alcool	Classes_2A	Classes_2B	Classes_4
5	Afrique septentrionale	4	CL1	CL1	CL1
3	Afrique occidentale	21	CL1	CL1	CL1
4	Afrique orientale	35	CL1	CL1	CL4
2	Afrique centrale	39	CL1	CL1	CL4
1	Afrique australe	101	CL2	CL1	CL3
6	Europe méridionale	145	CL2	CL2	CL2
9	Europe septentrionale	146	CL2	CL2	CL2
8	Europe orientale	160	CL2	CL2	CL2
7	Europe occidentale	176	CL2	CL2	CL2

La solution trouvée par l’algorithme consiste à séparer la région d’Afrique Australe de l’Europe pour en faire une classe à elle toute seule. Puis à diviser les 4 régions d’Afrique en deux paires.

DEUX DIMENSIONS

Examinons maintenant le cas d’une espace à deux dimensions en reprenant l’exemple utilisé dans l’introduction à l’ACP :

Consommation moyenne de lait et d'alcool en Europe et en Afrique en 2020 (en kCal/pers/jour)

	region	Lait	Alcool
1	Afrique australe	90	101
2	Afrique centrale	12	39
3	Afrique occidentale	26	21
4	Afrique orientale	71	35
5	Afrique septentrionale	134	4
6	Europe méridionale	310	145
7	Europe occidentale	446	176
8	Europe orientale	290	160
9	Europe septentrionale	380	146

Distance euclidienne non normée

Les distances euclidiennes correspondent ici à la distance entre les points dans le plan constitué par nos deux variables ou la consommation de lait est la coordonnée X et la consommation d’Alcool la coordonnée Y :

Matrice de distance

L’examen du graphique permet de deviner visuellement quelles unités sont les plus proches les unes des autres. On voit ainsi que le point n°1 semble plus proche du point n°5 que du point n°8, ce que l’on peut confirmer en calculant la distance euclidienne dont on rappelle la formule :

\(D_{ij}=\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}\)

\(D_{1,5}=\sqrt{(101-4)^2+(90-134)^2} = \sqrt{9409+1936} = 106.5\)

\(D_{1,8}=\sqrt{(101-160)^2+(90-290)^2} = = \sqrt{3481+40000} = 208.5\)

[1] 40000

[1] 208.521

La matrice de distance euclidienne complète est donc :

Distance euclidienne

	1	2	3	4	5	6	7	8	9
1	0	100	102	69	107	224	364	209	293
2	100	0	23	59	127	316	455	303	383
3	102	23	0	47	109	310	448	298	375
4	69	59	47	0	70	263	401	252	328
5	107	127	109	70	0	226	356	221	284
6	224	316	310	263	226	0	139	25	70
7	364	455	448	401	356	139	0	157	72
8	209	303	298	252	221	25	157	0	91
9	293	383	375	328	284	70	72	91	0

Classification k-means

L’application de la méthode k-means demande à l’utilisateur de fixer le nombre de classes souhaité. L’algorithme va ensuite tirer au sort des individus et procéder à des regroupements autour d’eux puis choisir la solution qui minimise les distance intra-classes et maximise les distances inter-classes. Si l’on opte pour pour 2 classes aboutira à la présence de deux groupes bien distincs :

Classification ascendante hiérarchique

La classification ascendante hiérarchique utilise un algoritjme différent. Elle commence par regrouper ensemble les individus les plus proches selon un critère (ici : la distance moyenne entre individus) puis opère des fusions d’individus et de classe jusqu’à regrouper pous les individus en une seule classe.

Comme on peut le voir, elle regroupe en premier les individus n°2 et n°3 qui sont effectivement les plus proches (\(D_{2,3} = 23\)), puis les individus n°7 et n°8 (\(D_{7,8} = 25\)). A l’étape suivante, l’algorithme regroupe la classe \((2,3)\) avec l’individu n°4 pour former un groupe \((2,3,4)\) où la distance moyenne entre les trois individus est égale à 43. Elle regroupe ensuite les individus n°7 et n°9 dont la distance est de 79, etc.

Sur le dendrogramme (arbre hiérarchique de regroupement, on peut repérer sur l’axe vertical la distance moyenne de regroupement des individus. On voit que le dernier regroupement entre les individus (1,2,3,4,5) et les individus (6,7,8,9) correspond à une distance moyenne proche de 300 ce qui souligne l’existence très nette de deux classes bien différentes.

Distance euclidienne normée

Supposons maintenant que nous ayons décidé en début d’analyse de standardiser nos variables en leur donnant à chacune une moyenne de zéro et un écart-type de 1. Le tableau de départ serait alors celui-ci :

Tableau standardisé

	région	Lait_std	Alcool_std
1	Afrique australe	-0.6482812	0.1352042
2	Afrique centrale	-1.1278317	-0.7848441
3	Afrique occidentale	-1.0417585	-1.0519549
4	Afrique orientale	-0.7650948	-0.8442020
5	Afrique septentrionale	-0.3777656	-1.3042262
6	Europe méridionale	0.7042971	0.7881417
7	Europe occidentale	1.5404364	1.2481659
8	Europe orientale	0.5813354	1.0107341
9	Europe septentrionale	1.1346629	0.8029812

Distance

Du même coup, les distances entre les individus se trouvent modifiés ce que montre tout d’abord le graphique

La matrice de distance euclidienne normée est désormais mesurée en nombre d’écart-type et on constate que les points se sont rapprochés dans le sens de la variable X (Lait) et éloignés dans le sens de la variable Y (Alcool).

Distance euclidienne normée

	1	2	3	4	5	6	7	8	9
1	0.00	1.04	1.25	0.99	1.46	1.50	2.46	1.51	1.90
2	1.04	0.00	0.28	0.37	0.91	2.41	3.35	2.48	2.76
3	1.25	0.28	0.00	0.35	0.71	2.54	3.46	2.62	2.86
4	0.99	0.37	0.35	0.00	0.60	2.20	3.11	2.29	2.51
5	1.46	0.91	0.71	0.60	0.00	2.36	3.19	2.51	2.59
6	1.50	2.41	2.54	2.20	2.36	0.00	0.95	0.25	0.43
7	2.46	3.35	3.46	3.11	3.19	0.95	0.00	0.99	0.60
8	1.51	2.48	2.62	2.29	2.51	0.25	0.99	0.00	0.59
9	1.90	2.76	2.86	2.51	2.59	0.43	0.60	0.59	0.00

Classification k-means

L’application de la méthode k-means donne des résultats proches de l’analyse précédente mais avec une opposition moins nette entre les deux groupes désormais

Classification ascendante hiérarchique

La classification ascendante hiérarchique conserve quant à elle la division en deux groupe mais on repère de légères modifications dans le bas de l’arbre. Ainsi, l’individu n°9 ne se regroupe plus en premier avec l’individu n°7 mais avec les individus n°6 et 8.

Méthode de Ward

La troisième méthode, qui est en pratique la plus utilisée, consiste à opérer une classification non plus à l’aide des distances euclidiennes (normées ou non) mais à l’aide du carré de ces distances euclidiennes. Pourquoi ?

Parce que, comme nous l’avons vu dans le cadre du cours sur l’Analyse en Composantes Principales, la somme des distance euclidiennes au carré est proportionnelle à la somme des variances des différentes variables du tableau. La méthode de Ward va donc consiste à minimiser la variance intra-classes et maximiser la variance inter-classes. Elle sera de ce fait très complémentaire avec l’ACP puisque cette dernière consiste précisément à concentrer la variance sur quelques axes significatifs.

Indiquons brièvement sans nous y attarder pour l’instant les résultats d’une ACP-CAH normée appliquée à notre tableau.

Bibliographie